package com.guli.gulimalltest;

import java.util.*;
import java.util.stream.Collectors;

public class rr {
    public int[] LIS (int[] arr) {
        // write code here
        List<LinkedList<Integer>> list = new ArrayList<>(arr.length);
        int count = 0;
        for(int i = 0;i<arr.length;i++){
            list.add(new LinkedList<>());
            list.get(i).add(0);
            for(int j=0;j<=i;j++){
                if(list.get(j).getLast()<arr[i]){
                    int temp = list.get(j).pollFirst();
                    list.get(j).addFirst(temp+1);
                    count = count > temp+1?count:temp+1;
                    list.get(j).addLast(arr[i]);
                }else if(list.get(j).getLast() > arr[i]){
                    int temp = list.get(j).pollLast();
                    int  temp1 = list.get(j).getLast();
                    if(temp1<arr[i])list.get(j).addLast(arr[i]);
                    else list.get(j).addLast(temp);
                }
            }
        }
        int finalCount = count;
        list.stream().filter(item->{
            return item.getFirst()== finalCount;
        }).collect(Collectors.toList());
        return new int[2];
    }
}
